var inorderTraversal = function (root, array = []) {
  if (root) {
    inorderTraversal(root.left, array);
    array.push(root.val);
    inorderTraversal(root.right, array);
  }
  return array;
};
function Node (data, left, right) {
  this.data = data
  this.left = left
  this.right = right
}
//展示节点
Node.prototype.show = function () {
  console.log(this.data)
}
//创建二叉树
/**
 *  root 根节点
 */
function Tree () {
  this.root = null
}
Tree.prototype = {
  insert: function (data) {
    var node = new Node(data, null, null);
    if (!this.root) {
      this.root = node;
      return;
    }
    var current = this.root;
    var parent = null;
    while (current) {
      parent = current;
      if (data < parent.data) {
        current = current.left;
        if (!current) {
          parent.left = node;
          return;
        }
      } else {
        current = current.right;
        if (!current) {
          parent.right = node;
          return;
        }
      }

    }
  },
  //二叉树前序遍历;首先访问根节点，然后遍历左子树，最后遍历右子树
  preOrder: function (node) {
    if (node) {
      node.show()
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  },
  //二叉树的中序遍历:首先方问左子树,然后根节点 ,最后右子树
  middleOrder: function (node) {
    if (node) {
      this.middleOrder(node.left)
      node.show()
      this.middleOrder(node.right)
    }
  },
  //二叉树的后序遍历:首先访问左子树 然后右子树 最后根节点
  laterOrder: function (node) {
    if (node) {
      this.laterOrder(node.left)
      this.laterOrder(node.right)
      node.show()
    }
  },
  //获取二叉树中的最小值
  getMin: function () {
    var current = this.root
    while (current) {
      if (!current.left) {
        return current
      }
      current = current.left
    }
  },
  //获取二叉树中的最大值
  getMax: function () {
    var current = this.root
    while (current) {
      if (!current.right) {
        return current
      }
      current = current.right
    }
  },
  getDeep: function () {
    deep = deep || 0
    if (node == null) {
      return deep
    }
    deep++
    var dleft = this.getDeep(node.left, deep)
    var dright = this.getDeep(node.right, deep)
    return Math.max(dleft, dright)
  }
}
var t = new Tree();
t.insert(1);
t.insert(null);
t.insert(2);
t.insert(3);
console.log(inorderTraversal(t, []));